package leetcode_100;

/**
 *@author 周杨
 *MedianOfTwoSortedArrays_4_ 寻找两个有序数组里的中位数
 *describe:用二分查找 找第一个数组里的k个元素 注意边界情况 AC 36%
 *see:https://www.youtube.com/watch?v=KB9IcSCDQ9k
 *2018年12月17日 下午3:54:59
 */
public class MedianOfTwoSortedArrays_4_ {
	
	public static void main(String[] args) {
		MedianOfTwoSortedArrays_4_ test=new MedianOfTwoSortedArrays_4_();
//		System.out.println(test.findMedianSortedArrays(new int[] {1,3}, 
//				new int[] {2}));
		System.out.println(test.findMedianSortedArrays(new int[] {1,2}, 
				new int[] {3,4}));
	}
	
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int n1=nums1.length;
		int n2=nums2.length;
		if(n1>n2) return findMedianSortedArrays(nums2, nums1);//默认去小的数组里二分搜索
		int left=0,right=n1;//去数组里二分搜索
		int k=(n1+n2+1)/2;//目的就是找到这个数
		int m1=0,m2=0;
		while(left<right) {
			m1=left+(right-left)/2;
			m2=k-m1;
			if(nums1[m1]<nums2[m2-1])
				left=m1+1;
			else
				right=m1;
		}
		m1=left;
		m2=k-left;
		//下面是边界情况 这两个元素有可能都在同一个数组中
		int c1=Math.max(m1<=0?Integer.MIN_VALUE:nums1[m1-1],
				m2<=0?Integer.MIN_VALUE:nums2[m2-1]);
		if((n1+n2)%2==1) return c1;
		int c2=Math.min(m1>=n1?Integer.MAX_VALUE:nums1[m1]
				, m2>=n2?Integer.MAX_VALUE:nums2[m2]);
		return (c1+c2)*0.5f;
	}
	
	
	
	/**
	 * describe:时间复杂度O(m+n) 给定两个指针 i j 分别从两个数组左往右遍历 当i+j等于预期值则停下 AC 5%
	 * 2018年8月23日 下午2:37:31
	 */
	public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
		int length=(nums1.length+nums2.length)/2;
		int i=0,j=0;
		boolean flag=true;
		if((nums1.length+nums2.length)%2==0){//
			flag=false;//偶数
			--length;
		}
		double result=0f;
		while(i+j<length){
			if(i==nums1.length){
				++j;
				continue;
			}
			if(j==nums2.length){
				++i;
				continue;
			}
			if(nums1[i]<nums2[j]){
				++i;
			}
			else{
				++j;
			}
		}
		if(flag){
			if(i==nums1.length)
				return nums2[j];
			if(j==nums2.length)
				return nums1[i];
			return nums1[i]<nums2[j]?nums1[i]:nums2[j];
		}
		else{
			for(int k=0;k<2;++k){
				if(i==nums1.length){
					result+=nums2[j++];
					continue;
				}
				if(j==nums2.length){
					result+=nums1[i++];
					continue;
				}
				result+=(nums1[i]<nums2[j]?nums1[i++]:nums2[j++]);
			}
		}
		return result/2;
    }
}	
